/*************************************************************
 * 
 * CopyRight(c)2007, http://www.moorwind.com/
 * email:ezhung@gmail.com
 * for free, but a email permission would be nice
 * 
 ************************************************************/
package kono.utils
{
	//哈希表，数组型， hash table built on a table
	public class HashTable
	{
		//哈希表已经使用的数量， total number that has been used in the table
		private var manyItems:uint;
		
		//唯一关键字， the key word		
		private var keys:Array;
		
		//关键字对应的数值， data of the key
		private var data:Array;
		
		//表中对应位置是否已经被使用， if the given cell in the table has been used
		private var hasBeenUsed:Array;
		
		//散列函数， a function used for hashing strings
		private function hash(key:*):int
		{
			return Math.abs(hashCode(key)) % data.length;
		}
		
		//再散列函数， a function used for  rehashing strings
		private function hash2(key:*):int
		{
			return 1 + (Math.abs(hashCode(key)) % (data.length - 2));
		}
		
		//返回给定string一个唯一的整数用于散列， return a number for the initialize  hashing function
		private static function hashCode(s:String):int
		{
			var _hash:int = 0;
			for(var i:uint = 0; i < s.length; i++)
			{
				_hash += (i + 1) * s.charCodeAt(i);
			}
			return _hash;
		}
		
		//用于遍历数组的辅助函数， a simple function uesd for help search all the items in an array
		private function nextIndex(i:uint, key:*):uint
		{
			if(i + 1 == data.length)
				return 0;
			else
				return (i + hash2(key))%data.length;
		}
		
		//用于找到某个具有指定关键字的对象的数组索引， for the use of finding the given key's index of the data array
		private function findIndex(key:*):int
		{
			var count:uint = 0;
			var i:int = hash(key);
			while((count < data.length) && hasBeenUsed[i])
			{
				if(key == keys[i])
					return i;
				count++;
				i = nextIndex(i, key);
			}
			
			return -1;
		}
		
		//填充数组
		private function fillNull():void
		{
			for(var i:uint = 0; i < data.length; i++)
			{
				data[i] = keys[i] = null;
				hasBeenUsed[i] = false;
			}
		}
		
		//使用符合capacity = 4k+3的素数的表长在避免冲突方面比较好
		public function HashTable(capacity:uint)
		{
			if(capacity == 0)
				throw new Error("Capacity is negative");
			keys = new Array(capacity);
			data = new Array(capacity);
			hasBeenUsed = new Array(capacity);
			fillNull();
		}
		
		//返回哈希表已使用的数目， return the total number has been used of the table
		public function get size():uint
		{
			return manyItems;
		}
		
		//添加数据， add a new data/key element into the hash table
		public function put(element:*, key:*):*
		{
			var index:int = findIndex(key);
			var answer:*;
			
			if(index != -1)
			{
				answer = data[index];
				data[index] = element;
				return answer;
			}
			else if(manyItems < data.length)
			{
				index = hash(key);
				while(keys[index])
					index = nextIndex(index, key);
				keys[index] = key;
				data[index] = element;
				hasBeenUsed[index] = true;
				manyItems++;
				return null;
			}
			else
			{
				throw new Error("Table is full");
			}
		}
		
		//删除具有给定关键字的数据， remove the data int the table that the given key number pointing to
		public function remove(key:*):*
		{
			var index:int = findIndex(key);
			var answer:* = null;
			if(index != -1)
			{
				answer = data[index];
				data[index] = null;
				keys[index] = null;
				manyItems--;				
			}
			return answer;
		}
		
		//检查是否包含指定关键字的数据， check if the  data exit based on the given key number
		public function contains(key:*):Boolean
		{
			return findIndex(key) != -1;
		}
		
		//返回哈希表的信息， return a string respreaenting the current hash table
		public function toString():String
		{
			return "[HashTable, size=" + data.length + "]";
		}
		
		//打印出哈希表的所有元素， print all the member of the table
		public function print():void
		{
			trace("HashTable: ");
			for(var i:uint = 0; i < data.length; i++)
			{
				trace("data:" + data[i] + " -key:" + keys[i]);
			}
		}
	}
}